﻿#pragma once
#include <iostream>
using namespace std;

template<class T>
struct SBnode
{
	T _key;
	SBnode<T>* _left;
	SBnode<T>* _right;
	SBnode(const T&k)
		:_key(k)
		,_left(nullptr)
		,_right(nullptr)
	{ }
};


template<class k>
class SBTree
{
public:
	typedef SBnode<k> Node;
	//数据的插入
	bool insert(const k& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = root;
		while (cur)
		{
			//左放小，右放大
			parent = cur;
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
				return false;
		}
		cur = new Node(key);		//找到了结点也要判断，判断放在结点的左边还是右边
		if (parent->_key < key)
			parent->_right = cur;
		else
			parent->_left = cur;
		return true;
	}

	bool find(const k& x)
	{
		Node* parent = nullptr;
		Node* cur = root;
		while (cur)
		{
			//左放小，右放大
			parent = cur;
			if (cur->_key < x)
			{
				cur = cur->_right;
			}
			else if (cur->_key < x)
			{
				cur = cur->_right;
			}
			else
				return true;
		}
		return false;
	}

	bool Erase(const k& key)
	{
		//删除叶子节点
		if (root == nullptr)
		{
			return false;
		}
		if (!find(key))
			return false;
		Node* parent = nullptr;
		Node* cur = root;
		while (cur)
		{
			//左放小，右放大
			parent = cur;
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
				break;
		}

		if (cur->_left == nullptr && cur->_right == nullptr)
		{
			delete cur;
			return true;
		}
		else if()
	}
	//打印函数
	void Printf()
	{
		_Printf(root);
		cout << endl;
	}
	void _Printf(Node* _root)
	{
		if (_root == nullptr)
			return;
		//采用中序遍历
		_Printf(_root->_left);
		cout << _root->_key << ' ';
		_Printf(_root->_right);
	}
private:
	Node* root = nullptr;
};

void test()
{
	SBTree<int> t1;
	int arr[] = { 3,8,9,20,25,28,30 };
	for (auto& e : arr)
		t1.insert(e);
	t1.Printf();
	cout << t1.find(3) << endl;			//1
	cout << t1.find(30) << endl;		//1
	cout << t1.find(20) << endl;		//1
	cout << t1.find(200) << endl;		//0
}
